문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 불완전성 정리 (문단 편집) === 제1정리 === 제1불완전성 정리 증명의 실질적인 첫 단계는 임의의 식을 [[자연수]]로 번역하는 [[알고리즘|절차]]를 만드는 것이다.[* 나중에 [[앨런 튜링]]도 이 방법을 차용하여 [[튜링 머신]]을 만들었다.] 그 방식은 다양하나, 요체는 모든 식 각각에 고유한 자연수를 부여하는 것이다. 이처럼 그 식과 일대일로 대응하는 자연수를 그 식의 괴델수(Godel number)라고 부른다. 산술식 [math(1+0=1)]를 예로 들어보자. 이 식에 등장하는 기호의 유형은 '[math(1)]', '[math(+)]', '[math(0)]', '[math(=)]'로 네 가지다. 이때 각 기호의 유형마다 고유한 자연수를 부여하자. 그 예는 다음과 같다.[* 서로 다른 기호들에는 다른 양의 정수가 부여되면 되니까 산술명제들과 그것들을 이루는 기호들의 집합에서 양의 정수로 가는 단사함수(injection)로 이해해도 상관 없다. 또한 굳이 괴델이 보인 방식만 있는건 아니고 다른 방식들을 얼마든지 정할 수 있다. [[위키백과]]에서는 기초적인 10개의 '불변부호', 즉 '('나 '0', 's' 같은 것들에 미리 1~10을 할당하고, 나머지 경우에는 변수마다 종류를 나눠 [math(n)]번째 종류의 [math(k)]번째 변수에 해당하는 괴델수를 [math((10\text{이후의 }k\text{번째 소수})^n)]으로 제시했다. 이렇게 하면 모든 기호들마다 동일한 수가 겹칠 일이 없다. 영어가 된다면 직접 영어 위키백과에서 괴델 수 항목을 읽어봐도 도움이 된다.] || 기호 유형 || 괴델수 || || '[math(0)]' || 3 || || '[math(1)]' || 4 || || '[math(+)]' || 5 || || '[math(=)]' || 6 || 이때 식 [math(1+0=1)]은 5개의 기호로 이루어져 있으므로, 그 길이 [math(n=5)]라고 할 수 있다. 그 길이에 해당하는 최초의 [[소수(수론)|소수]]들, 즉 가장 작은 소수 5개는 2, 3, 5, 7, 11이다. 이 소수들은 각 기호의 위치를 나타낸다. 이에 의거하여 각 위치마다 놓인 기호는 다음과 같이 [[지수(수학)|지수]]를 사용해 표현가능하다. [math(\displaystyle\text{괴델 수}=\prod^n_{k=1}P_k^{(k\text{번째로 오는 기호 유형에 상응하는 괴델수})}\quad(\text{단, }P_k\text{는 }k\text{번째 소수}))] 예컨대 [math(1+0=1)]의 첫 자리에 나타나는 '1'은 [math(2^4=16)]으로 번역가능하다. 그리고 이렇게 번역된 각 자연수들을 다 곱함으로써 식 전체를 그 괴델수로 번역할 수 있다. 이를테면 [math(1+0=1)]의 괴델수는 [math(2^4\times3^5\times5^3\times7^6\times11^4=837134518374000)]이 된다. 이처럼 임의의 식에 상응하는 괴델수를 계산해낼 수 있다. 그리고 똑같은 원리에 의거하여 여러 식들의 나열, 이를테면 [[증명]]에 해당하는 괴델수 또한 계산하는 것이 가능하다. 이를 토대로 다음과 같은 개념을 정의하자: * 식 '[math(Dem(x, y))]': '괴델수가 [math(y)]인 명제의 증명은 괴델수가 [math(x)]이다' * 예. '[math(\exists x Dem(x, y))]':' '괴델수가 [math(y)]인 명제의 증명이 존재한다' * 함수 [math(sub(n, k, n))]: 괴델수가 [math(n)]인 식의 변항 중 괴델수가 [math(k)]인 변항에 ([math(n)]을 나타내는 기호인) '[math(n)]'을 대입해서 얻은 식의 괴델수[*주의 [math(n)]을 나타내는 기호를 '[math(n)]'라고 적기하는 것은 엄밀하지 않다. 변수 [math(n)]을 나타내는 기호는 변항이 아닌 [math(n)]을 나타내는 [[숫자]]일 것이기 때문이다. 마찬가지로 '[math(Dem(x, sub(n, 17, n)))]'라는 표현은 엄밀하지 않다. [math(sub(y, 17, y))]는 함수값이며, [math(Dem)]의 두번째 변항은 기호가 되어야 하기 때문이다.] * 예. 식 '[math(\exists x (x=y))]'의 괴델수가 [math(m)]이라고 하고, '[math(y)]'의 괴델수가[math(j)]라고 하자. [math(sub(m, j, m))]는 '[math(\exists x (x=y))]'에서 '[math(y)]'를 '[math(m)]'으로 교체한 식의 괴델수다.[*주의] 변항 '[math(y)]'의 괴델수를 17이라고 가정하라. 이때 식 '[math(\neg ∃xDem(x, sub(y, 17, y)))]'의 의미는 정의상 '괴델수가 [math(sub(y, 17, y))]인 식의 증명은 존재하지 않는다'가 될 것이다.[*주의] 이때 '[math(\neg ∃xDem(x, sub(y, 17, y)))]'의 괴델수는 [math(n)]이라 하자. 그렇다면 [math(n)]을 나타내는 기호 '[math(n)]'을 포함하는 다음 식 [math(G)] 또한 생각할 수 있다. * [math(G)]: '[math(\neg ∃xDem(x, sub(n, 17, n)))]' * 의미: '괴델수가 [math(sub(n, 17, n))]인 식의 증명은 존재하지 않는다' 이때 [math(G)]의 괴델수를 [math(g)]라고 하자. 그런데 [math(g = sub(n, 17, n))]이다. 왜냐면 가정상 괴델수가 [math(n)]인 식은 '[math(\neg ∃xDem(x, sub(y, 17, y)))]'인데, 정의상 [math(sub(n, 17, n))]은 이 식에서 '[math(y)]'를 '[math(n)]'으로 대체한 식의 괴델수이고, '[math(y)]'를 '[math(n)]'으로 대체한 바로 그 식이 [math(G)]이기 때문이다. 그 [math(G)]의 괴델수가 [math(g)]이므로, 곧 [math(g)]는 [math(sub(n, 17, n))]와 같다. 그러므로 [math(G)]의 의미는 '괴델수가 [math(g)]인 식의 증명은 존재하지 않는다'라고도 볼 수 있다. 그런데 괴델수가 [math(g)]인 식은 바로 [math(G)]다. 따라서 '''[math(G)]의 의미는 '[math(G)]의 증명은 존재하지 않는다'는 것이다.''' 먼저 [math(G)]의 증명이 존재한다고 가정해보자. 그러면 명제 [math(G)]는 거짓인데, 이로부터 [math(G)]의 부정의 증명 또한 있음을 보일 수 있다. 하지만 이는 무모순성을 위반한다.[* 그냥 모순을 받아들이면 안 되나 싶을 수도 있지만 모순을 받아들이는 순간 모든 게 참으로 귀결되는 쓸모없는 공리계가 되어버린다. 이를 '''[[폭발 원리]]'''(Principle of Explosion)라고 하는데, 직관주의 논리체계에서는 추론규칙으로 사용하며, 스탠다드 논리체계에서는 다른 공리들에 의해 연역된다. 이 논리학 법칙에 대해 자세히 알고 싶다면 [[https://en.wikipedia.org/wiki/Principle_of_explosion|위키백과 영문판]] 참조. 나무위키의 [[명제 논리]] 문서에도 간략한 설명과 증명이 실려 있다.] 역으로 명제 [math(G)]의 부정에 대한 증명이 존재한다고 가정할 경우에도 무모순성이 위반된다.[* 괴델의 최초의 증명에서는 [math(\neg G)]의 부정으로부터 ω-모순성, 즉 산술을 해석하는 이론 [math(T)] 안에 자연수에 대한 논리식 [math(P)]가 있을 때, [math(T)]로부터 논리식 [math(P(0),\,P(1),\,P(2),\dots)] 라는 식으로 [math(P(n))]의 성립을 모두 증명가능한 동시에 [math(\exists n:\neg P(n))]도 증명가능하다는 것을 보였다. 보다 일반적인 모순성을 도출시킨 것은 존 버클리 로써(John Barkley Rosser)이며, 이때문에 제1불완전성 정리는 괴델-로써 정리라고도 한다.] 즉 대우를 취할 경우, 주어진 증명 체계가 무모순적이라면 [math(G)]와 그 부정 둘 중 어느 것도 증명할 수 없으므로 불완전하다는 점이 도출된다. 그리고 [math(G)]의 의미상 [math(G)]는 참이 된다. 따라서 참이지만 증명할 수 없는 명제가 있다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기